﻿#define _CRT_SECURE_NO_WARNINGS 1
//day27-01 牛客：kotori和⽓球，题号：500541
//解法：组合数学
//typedef long long LL;
//LL n, m;
//int main()
//{
//    cin >> n >> m;
//    LL ret = 1;
//    ret *= n;
//    for (LL i = 0; i < m - 1; i++)
//    {
//        ret = (ret * (n - 1)) % 109;
//    }
//    cout << ret;
//    return 0;
//}


//day27-02 牛客：走迷宫，题号：2373924
//解法：BFS
//const int N = 1010;
//char grid[N][N];
//bool vis[N][N] = { 0 };
//int dx[4] = { 0,0,1,-1 };
//int dy[4] = { 1,-1,0,0 };
//int n, m;
//int x1, y_1, x2, y2;
//
//int bfs()
//{
//    queue<pair<int, int>> q;
//    q.push({ x1,y_1 });
//    vis[x1][y_1] = true;
//    int path = 0;
//    while (q.size())
//    {
//        path++;
//        int nums = q.size();
//        for (int i = 0; i < nums; i++)
//        {
//            auto [a, b] = q.front(); q.pop();
//            for (int k = 0; k < 4; k++)
//            {
//                int x = a + dx[k], y = b + dy[k];
//                if (x >= 1 && x <= n && y >= 1 && y <= m && grid[x][y] == '.' && !vis[x][y])
//                {
//                    if (x == x2 && y == y2)
//                    {
//                        return path;
//                    }
//                    q.push({ x,y });
//                    vis[x][y] = true;
//                }
//            }
//        }
//    }
//    return -1;
//}
//int main()
//{
//    cin >> n >> m;
//    cin >> x1 >> y_1 >> x2 >> y2;
//    for (int i = 1; i <= n; i++)
//        for (int j = 1; j <= m; j++)
//            cin >> grid[i][j];
//    cout << bfs();
//    return 0;
//}


//day27-03 牛客：主持人调度（二），题号：1267319
//解法：贪心+优先级队列
//int minmumNumberOfHost(int n, vector<vector<int> >& startEnd)
//{
//	sort(startEnd.begin(), startEnd.end());
//	priority_queue<int, vector<int>, greater<int>> heap; // 创建⼀个⼩根堆
//	heap.push(startEnd[0][1]); // 先把第⼀个区间放进去
//	for (int i = 1; i < n; i++) // 处理剩下的区间
//	{
//		int a = startEnd[i][0], b = startEnd[i][1];
//		if (a >= heap.top()) // 没有重叠
//		{
//			heap.pop();
//			heap.push(b);
//		}
//		else // 有重叠
//		{
//			heap.push(b); // 重新安排⼀个⼈
//		}
//	}
//	return heap.size();
//}
